package com.Sep_Twentytree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 131. 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 *
 * 回文串 是正着读和反着读都一样的字符串。
 *
 * https://leetcode.cn/problems/palindrome-partitioning/
 *
 * 2022/09/23 12:12
 */

public class Solution131 {

    List<List<String>> list=new ArrayList<>();
    Deque<String> deque=new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return list;
    }

    public void backtracking(String s,int startIndex){
        if (startIndex>=s.length()) {
            list.add(new ArrayList<>(deque));
            return;
        }
        for (int i=startIndex;i<s.length();i++)
        {
            if (judge(s,startIndex,i))
            {
                String str=s.substring(startIndex,i+1);
                deque.offer(str);
                backtracking(s,i+1);
                deque.removeLast();
            }
        }
    }

    public boolean judge(String s,int left,int right){
        for (int i=left,j=right;i<j;i++,j--)
        {
            if (s.charAt(i)!=s.charAt(j))
            {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution131 solution40=new Solution131();
        System.out.println(solution40.partition("aab"));
    }
}
